Modulo multiplication is an arithmetic process of determining the remainder of the product of two numbers. Modulo multiplication is a particularly versatile tool that has many applications in the computer field. For example, specific implementations of cryptography use modulo multiplication to perform certain processing functions. The remainder of modulo multiplication, also known as the residue of the modulo of the product of two numbers is typically used in many data processing applications.
In the field of cryptography many different types of encryption and decryption have been developed to prevent unauthorized file access. IDEA, a block cipher, developed by Xuejia Lai and James Massey and patented under International Patent PCT/CH91/00117 on Nov. 28, 1991, and a patent held by Ascom-Tech AG of Magenwil, Switzerland, is one example of a type of encryption/decryption method that utilizes modulo multiplication. On page 320 of Applied Cryptography, Bruce Schneier describes IDEA as a cipher that operates on 64-bit plaintext blocks and has a key of 128 bits in length. IDEA uses the same algorithm for both encryption and decryption.
IDEA uses an algorithm that includes a combination of operations from different algebraic groups. The three algebraic groups include "XOR," "Addition modulo 2.sup.16," and "multiplication modulo 2.sup.16 +1." The three algebraic groups of IDEA can be implemented in both hardware and software to perform the encryption/decryption of this cipher.
Although IDEA is effective in its use of multiplication modulo 2.sup.16 +1, the conventional process for determining a remainder from the division of two binary numbers requires reductions that are both costly and time consuming. Furthermore, a conventional hardware implementation of modulo multiplication requires a divider circuit. An example of a conventional process for performing modulo multiplication is shown below.
(1) A*B mod M PA1 (2) Where: M=2.sup.N +1 PA1 (3) N=4 PA1 (4) M=2.sup.4 +1 PA1 (5) M=17 (base 10) PA1 (6) A=01010 (base 2)=10 (base 10) PA1 (7) B=01110 (base 2)=14 (base 10) ##EQU1##
Line 1 above shows the modulo multiplication equation of (A*B mod M), where A, B and M are each binary numbers. Line 2 shows that modulus "M" is equal to two to the power of N, plus one, where "N+1" is the length in bits of both variables A and B. Line 3 shows that in this example the bit length of N is equal to four. Hence, in line 4, "M" is equal to two to the fourth power plus one. Line 5 shows that the result of the equation of line 4 has the base 10 value of 17. Lines 6 and 7 show both the binary and corresponding decimal values chosen for the variables "A" and "B" of line 1. Line 8 shows multiplication of the binary values of variable "A" and "B." Line 9 shows that the resulting product of the equation of line 8 is the binary value "10001100."
FIG. 1 shows an example of a conventional process for determining the resulting modulus of the product of variables "A" and "B." As shown, a conventional process for this example requires four successive reductions of the product of A and B by modulus "M." The result of the four reductions yields the resulting modulus, also known as a remainder or residue, having a binary value "00000100."
A conventional hardware circuit of the modulo operation of FIG. 1 would include a divider circuit to perform the successive reductions required to determine the remainder of the product of "A" and "B." The four successive reductions would require four repetitive cycles of a divider circuit. One of ordinary skill in the art will understand, that as "A," "B" and the resulting product of "A" and "B" grow larger, the number of repetitive cycles needed to determine the remainder will also increase. It will be appreciated that a need to perform numerous cycles of a divider circuit to determine a remainder is costly, slow and requires excessive processing resources.
Therefore, there is a need to provide a system and method for performing fast and efficient modulo multiplication that minimizes processing requirements.